package main.Q1301_1400;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class Q1331_1340 {
    public static void main(String[] args) {
        System.out.println("Question1331：");
        System.out.println("Question1332：");
        System.out.println("Question1333：");
        System.out.println("Question1334：");
        System.out.println("Question1335：");
        System.out.println("Question1336：");
        System.out.println("Question1337：矩阵中战斗力最弱的K行");
        System.out.println("Question1338：数组大小减半");
        System.out.println("Question1339：");
        System.out.println("Question1340：");
    }
}

class Question1337 {
    public int[] kWeakestRows(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] all = new int[m][2];
        for (int i = 0; i < m; i++) {
            int cur = 0;
            for (int j = 0; j < n; j++) cur += mat[i][j];
            all[i] = new int[]{cur, i};
        }
        Arrays.sort(all, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = all[i][1];
        return ans;
    }
}

class Question1338 {
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        int[][] nums = new int[counts.size()][2];
        int index = 0;
        for (int key : counts.keySet()) {
            nums[index][0] = key;
            nums[index][1] = counts.get(key);
            index++;
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return o2[1] - o1[1];
                }
                return o2[0] - o1[0];
            }
        });
        int result = 0, count = 0;
        for (int[] cur : nums) {
            if (count < arr.length / 2) {
                count += cur[1];
                result++;
                continue;
            }
            break;
        }
        return result;
    }
}